package problem57;

import java.util.ArrayList;
import java.util.List;

//57.插入区间
//https://leetcode.cn/problems/insert-interval/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        List<int[]> list = new ArrayList<>();
        int x = newInterval[0], y = newInterval[1];
        boolean flag = false;
        if(n != 0 && intervals[0][0] > y) {
            flag = true;
            list.add(newInterval);
        }
        int[] tmp = new int[2];

        for(int i = 0; i<n; i++) {
            if(intervals[i][0] > y) {
                if(!flag) {
                    list.add(newInterval);
                    flag = true;
                }
                list.add(intervals[i]);
            }else if(intervals[i][1] < x) {
                list.add(intervals[i]);
            }else if(x <= intervals[i][1]){
                // x intervals[i][1]
                tmp[0] = Math.min(intervals[i][0], x);
                int j = i;
                while(j+1 < n && intervals[j+1][0] <= y) {
                    j++;
                }
                tmp[1] = Math.max(intervals[j][1], y);
                list.add(tmp);
                flag = true;
                i = j;
            }
        }

        if(n == 0) {
            list.add(newInterval);
        }
        if(n != 0 && intervals[n-1][1] < x) {
            list.add(newInterval);
        }
        
        int m = list.size();
        int[][] ret = new int[m][2];
        for(int k = 0; k<m; k++) {
            ret[k] = list.get(k);
        }
        return ret;
    }
}